/**
 * Creat with IntelliJ IDEA
 * Description:
 * User:WZW
 * Date:2022-02-27
 * Time:10:48
 */

class Node{
    int val;
    Node left;
    Node right;

    public Node(int val){
        this.val = val;
    }
}

public class BST {
    public Node root = null;

    public Node search(int val) {
        Node cur = root;
        while (cur != null) {
            if (cur.val == val) return cur;
            if (cur.val < val) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        return null;
    }

    public boolean insert(int val){
        if (root == null){
            root = new Node(val);
            return true;
        }
        Node cur = root;
        Node p = null;
        while (cur != null){
            if (cur.val == val)return false;
            p = cur;
            if (cur.val < val){
                cur = cur.right;
            }else {
                cur = cur.left;
            }
        }
        cur = new Node(val);
        if (p.val > val){
            p.left = cur;
        }else {
            p.right = cur;
        }
        return true;
    }

    public void remove(int key){
        Node cur = root;
        Node p = null;
        while(cur!=null){
            if (cur.val == key){
                removeNode(cur,p);
                break;
            }else if (cur.val < key){
                p = cur;
                cur = cur.right;
            }else {
                p = cur;
                cur = cur .left;
            }
        }
    }

    public void removeNode(Node cur, Node p){
        if (cur.left == null){
            if (cur == root){
                root = cur.right;
            }else if (cur == p.left){
                p.left = cur.right;
            }else {
                p.right = cur.right;
            }
        }else if (cur.right == null){
            if (cur == root){
                root = cur.left;
            }else if (cur == p.left){
                p.left = cur.left;
            }else {
                p.right = cur.left;
            }
        }else {
            Node target = cur.right;
            Node targetParent = cur;
            while (target.left != null){
                targetParent = target;
                target = targetParent.left;
            }
            cur.val = target.val;
            if (target == targetParent.right){
                targetParent.right = target.right;
            }else {
                targetParent.left = target.right;
            }
        }
    }

    public void inOrder(Node root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    public static void main(String[] args) {
        int[] tree = {10,2,34,6,4,24};
        BST bst = new BST();
        for (int i:tree) {
            bst.insert(i);
        }
        bst.inOrder(bst.root);
        System.out.println();
        bst.remove(34);
        bst.inOrder(bst.root);
        System.out.println();
        System.out.println(bst.search(34));
    }

}
